package srcInterviewPrep;

public final class LongestCommonSubsequence
{
    public static int FindLCSLength(char[] a, char[] b)
    {
        // null check for a and b

        char[] shorter = a.length < b.length ? a : b;
        char[] longer = shorter == a ? b : a;

        int n = shorter.length;

        int[] br = new int[n+1];
        int[] tr = new int[n+1];

        for (int j = 0; j <= n; ++j)
        {
            br[j] = 0;
        }

        for (int i = 1; i <= longer.length; ++i)
        {
            tr[0] = 0;

            for (int j = 1; j <= shorter.length; ++j)
            {
                if (shorter[j-1] == longer[i-1])
                {
                    tr[j] = 1 + br[j-1];
                }
                else
                {
                    tr[j] = Math.max(tr[j-1], br[j]);
                }
            }

            // swap tr and br
            int[] t = tr;
            tr = br;
            br = t;
        }

        System.out.println("tr: " + tr[n]);
        System.out.println("br: " + br[n]);
        System.out.println();
        return tr[n];
    }
}
